package 剑指offer;

public class Leedocode148排序链表 {
    public ListNode sortList(ListNode head) {
        if(head == null){
            return head;
        }
        if(head.next == null){//此时已经将链表拆分为只有一个节点的链表，有序，开始合并
            return head;
        }
        //此时已经找到中间节点，将左右两边断开
        ListNode mid = middle(head);
        ListNode x = head;
        while(x.next != mid){
            x = x.next;
        }
        x.next = null;
        //将左右两边的链表合并成有序链表
        ListNode lastv = sortList(mid);
        ListNode prev = sortList(head);
        //此时将左右链表的链表合并成大的有序链表
        return merge(prev,lastv);

    }
    //递归
    public ListNode merge(ListNode l1,ListNode l2){
        //如果有一个链表为空，则直接返回非空链表
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        //否则都不为空
        if(l1.val <= l2.val){
            l1.next = merge(l1.next,l2);
            return l1;
        }else{
            l2.next = merge(l1,l2.next);
            return l2;
        }
    }
    //迭代
    public ListNode merge1(ListNode l1,ListNode l2){
        ListNode dummyHead = new ListNode(-1);
        ListNode tail = dummyHead;
        while (l1 != null && l2 != null){
            if (l1.val <= l2.val){
                tail.next = l1;
                tail = l1;
                l1 = l1.next;
            }else {
                tail.next = l2;
                tail = l2;
                l2 = l2.next;

            }
        }
        if (l1 != null){
            tail.next = l1;
        }
        if (l2 != null){
            tail.next = l2;
        }
        return dummyHead.next;
    }
    public ListNode middle(ListNode head){
        //否则说明链表无序，需要继续归
        //是哟个快慢指针，找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
